\chapter {Architettura del tool}
\label {architettura}

Nella definizione dell'architettura del tool si \`e cercato di seguire la struttura tipica di un compilatore. Sono state cio\`e create una serie di fasi che operano in sequenza l'una dopo l'altra e che permettono di ottenere, a partire dal dato in ingresso, dei risultati che consentono di agevolare il calcolo del risultato finale e di effettuare una netta separazione logica tra i vari compiti che \`e necessario svolgere.

L'architettura del tool \`e rappresentata in figura~\ref{fig:architettura} e come si pu\`o notare sono presenti quattro fasi che permettono, a partire dall'interfaccia che rappresenta un progetto, di individuare dapprima delle rappresentazioni intermedie del dato in ingresso, successivamente di calcolare il valore di uguaglianza tra due progetti in base ad una determinata distanza.
\begin{figure}
  \begin{center}
    \includegraphics[width=\textwidth]{img/architettura.eps}
  \end{center}             
  \caption{Architettura del tool}
  \label{fig:architettura}
\end{figure}

Il tool ricever\`a in ingresso una rappresentazione del programma da confrontare. Non verr\`a quindi analizzato direttamente il codice sorgente ma verr\`a estratta un'interfaccia che sintetizza tutti i tipi e le funzioni utilizzate da ciascun modulo che compone il progetto. Questa estrazione verr\`a effettuata mediante uno script esterno al tool.

A questo livello l'interfaccia \`e vista come un semplice file di testo all'interno del quale saranno elencati i moduli che definiscono dichiarazioni di funzioni, tipi o sotto moduli. 
Tramite un parser sar\`a possibile definire la struttura grammaticale delle informazioni contenute nel file mediante un albero informatico (definito albero di sintassi astratta)\footnote{Questa fase \`e la stessa che viene effettuata nelle applicazioni, descritte nell'introduzione di questa tesi, che utilizzano un approccio orientato ai token per il calcolo della similarit\`a tra due programmi.}, il quale rappresenter\`a i dati esattamente come compaiono all'interno dell'interfaccia, ovvero saranno presenti tanti sotto alberi quanti sono i moduli che compongono un progetto.

Il passo successivo \`e la ristrutturazione di questo albero con lo scopo di eliminare la modularit\`a che lo caratterizza. L'obiettivo \`e quello di inserire all'interno di una tabella tutte le funzioni che appartengono ad un determinato progetto. Per eliminare la possibilit\`a di avere delle ambiguit\`a su funzioni omonime che sono definite in moduli distinti, queste verranno qualificate anteponendo al loro nome il percorso del modulo nel quale sono definite. Il blocco resolver si occupa di questa operazione creando, per ogni progetto, due tabelle, una che contiene tutte le funzioni qualificate e una contenente tutti i tipi definiti dall'utente anch'essi qualificati.
 
Ottenute le tabelle, per avvicinarsi alla grammatica dei tipi di riferimento mostrata nel capitolo precedente verr\`a modificata la struttura dei tipi, mantenendone comunque la semantica. Come vedremo in seguito, ogni tipo, che a questo livello chiameremo \textit{tipo utente}, la cui struttura \`e quella tipica del linguaggio $\OCaml$, verr\`a trasformato in una forma sintatticamente differente (\textit{tipo interno}) che permetter\`a di applicare la teoria degli isomorfismi vista nel capitolo~\ref{isomorfismi}. 

Il tool dovr\`a essere in grado di calcolare il livello di similarit\`a tra tutte le coppie di una lista di interfacce che verranno fornite dall'utente. 
L'ultima fase \`e quindi quella del calcolo dell'equivalenza. Lo scopo \`e l'individuazione del numero di funzioni, nei due progetti, che condividono due tipi che sono considerati isomorfi. Come vedremo nella sezione~\ref{sez:calcolo.equivalenze}, l'utente potr\`a specificare una metrica di distanza la quale permetter\`a di calcolare in modi diversi il grado di similitudine tra due progetti. 
                                                                         
																		 
\section{Estrazione delle interfacce}
\label {sez:estrazione}
La prima operazione da compiere per confrontare due progetti utilizzando il tool \textit{isotype} \`e quella di estrarre l'interfaccia del progetto che si desidera analizzare. Questo pu\`o essere effettuato utilizzando direttamente il compilatore di $\OCaml$, mediante l'opzione \texttt{-i} infatti, il compilatore \texttt{ocamlc} permette di ottenere l'interfaccia di un modulo {.ml}.
Ad esempio un modulo che contiene la definizione di un tipo per la rappresentazione di un albero informatico e una funzione per la memorizzazione delle etichette in una lista potrebbe essere:

\begin{verbatim}
type 'a tree = Empty | Node of 'a * 'a tree * 'a tree
let rec labels =
  function
    Empty -> []
  | Node(a, t1,t2) -> a::(labels t1) @ (labels t2)
\end{verbatim}
il quale produrrebbe l'interfaccia:
\begin{verbatim}
type 'a tree = Empty | Node of 'a * 'a tree * 'a tree
val labels : 'a tree -> 'a list
\end{verbatim}

Generalmente un progetto, per\`o, \`e composto da numerosi moduli che interagiscono tra loro. \`E stato necessario pertanto realizzare uno script che permettesse, a partire da una cartella contenente i sorgenti che compongono il progetto da analizzare, di estrarre un unico file, con estensione \textit{.if}, contenente tutte le informazioni ricercate.
Supponendo che il tipo e la funzione dell'esempio precedente, siano inseriti all'interno di un modulo denominato \textit{Tree}, il quale a sua volta \`e contenuto all'interno del modulo \textit{Syntax}, la struttura del file estratto diventerebbe:

\begin{verbatim}
module Syntax : 
sig
   module Tree :
   sig
    type 'a tree = Empty | Node of 'a * 'a tree * 'a tree
    val labels : 'a tree -> 'a list
   end
end
module NomeModulo :
sig
 ...
 ...
end
module ...
\end{verbatim}

Si verr\`a cio\`e a creare una struttura composta da definizioni di tipo e di funzioni inserite all'interno di moduli i quali potranno essere innestati all'interno di altri moduli. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Un'ulteriore precisazione va fatta sul modo con cui vengono estratte le interfacce, in particolare su come vengono gestite le variabili di tipo. Il compilatore \textit{ocamlc}, infatti, assegna i nomi delle variabili di tipo in modo del tutto autonomo all'utente. Questo significa che i nomi delle variabili definiti dall'utente all'interno in un tipo polimorfo vengono ridefiniti durante l'estrazione. Ad esempio le due definizioni:
%\begin{verbatim}
%type 'a my_list_a = Nil | Cons of 'a * 'a my_list_a
%type 'b my_list_b = Nil | Cons of 'b * 'b my_list_b
%\end{verbatim}
%portano entrambe allo stesso risultato:
%\begin{verbatim}
%type 'a my_list_a = Nil | Cons of 'a * 'a my_list_a
%type 'a my_list_b = Nil | Cons of 'a * 'a my_list_b
%\end{verbatim}
%questa caratteristica \`e risultata molto utile in quanto ha permesso di rendere il sistema insensibile ad eventuali modifiche sul nome delle variabili effettuate da un programmatore che plagia del codice.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section {Rappresentazione delle interfacce}
Una volta ottenuta l'interfaccia, questa verr\`a scansionata con lo scopo di ottenerne una rappresentazione che possa facilitare le operazioni successive.
Per fare questo \`e stato definito un parser che ha permesso di ottenere un albero di sintassi astratta\footnote{Questo tipo di struttura viene spesso utilizzata all'interno dei compilatori per descrivere la sintassi di una espressione.} (AST) per la rappresentazione di ciascun progetto.
La struttura di questo albero \`e la seguente:

\begin{verbatim}
qname : 
	  Id (string)
	| Segment (string, qname)
	| Functor (string, string, qname)
name : 
	  string
tvar : 
	  string
type_expr : 
	  Ref (type_expr list, qname)
	| Var (tvar)
	| Arrow (type_expr, type_expr)
	| Tuple (type_expr list)
constructor : 
	  Constructor (name, type_expr list)
field : 
	  Field (name, type_expr)
type_body : 
	  Abstract
	| Alias (type_expr)
	| Algebraic (constructor list)
	| Record (field list)
type_decl : 
	  tvar list, name, type_body
value_decl : 
	  name, type_expr
entity : 
	  Type (type_decl list)
	| Value (value_decl)
	| Exception (constructor)
	| Module (name, entity list)
\end{verbatim}

Ogni progetto sar\`a cio\`e composto da una lista di moduli i quali saranno caratterizzati da un nome e da una lista di entit\`a che potranno essere tipi, funzioni, eccezioni o moduli innestati. 

Per quanto riguarda i tipi, saranno definiti mediante una lista costituita da un insieme di variabili di tipo (eventualmente vuota), un nome e dalla definizione del corpo del tipo. Questo potr\`a essere astratto, un alias, un tipo algebrico oppure un record. Gli alias verranno definiti mediante un'espressione di tipo che potr\`a essere un riferimento, una variabile, un tipo freccia o una tupla.

Le funzioni saranno identificate dal nome e da un'espressione di tipo definita come nel caso precedente.

Nell'esempio del modulo contenente la definizione del tipo albero e della funzione che opera sulle etichette, la prima fase del tool permetterebbe di arrivare ad un albero la cui struttura \`e mostrata in figura~\ref{fig:ast}.
\begin{figure}
  \begin{center}
    \includegraphics[width=\textwidth]{img/ast.eps}
  \end{center}             
  \caption{Rappresentazione dell'ast del modulo ``albero binario''}
  \label{fig:ast}
\end{figure}

Questa rappresentazione permette di semplificare la fase successiva ovvero la rappresentazione tabellare delle funzioni e dei tipi presenti in un modulo. Verranno infatti raccolte all'interno di una tabella hash tutte le funzioni e i tipi in modo che la ricerca di queste due informazioni risulti estremamente efficiente. Tuttavia in questa conversione verr\`a persa la modularit\`a dell'interfaccia.
A questo livello l'interfaccia \`e infatti altamente strutturata, possono essere presenti moduli all'interno di altri moduli assieme a funzioni e definizioni di tipo. Il problema \`e che \`e possibile che siano presenti due moduli distinti che definiscono due funzioni, diverse, le quali per\`o condividono lo stesso nome. Questa situazione \`e estremamente frequente e, nell'ambito della struttura di un programma, non implica alcuna ambiguit\`a in quanto queste saranno discriminate dal modulo di appartenenza. Durante la fase di appiattimento, nella quale verr\`a eliminata la modularit\`a che caratterizza i file di interfaccia, per evitare di confondere due funzioni definite in questo modo, \`e necessario differenziare gli identificatori. Questo verr\`a effettuato qualificando i nomi delle funzioni e dei tipi con il nome del modulo all'interno del quale questi sono definiti. Questa qualificazione avverr\`a anteponendo al nome della funzione il \textit{percorso} del modulo che la contiene (lo stesso avverr\`a per le dichiarazione di tipo).

Supponendo di avere a disposizione un'interfaccia che definisce due moduli:
\begin{itemize}
\item \textit{Syntax}: che contiene il modulo \textit{Tree} nel quale sono definiti un tipo per la rappresentazione di un albero e una funzione \textit{labels}, la quale permette di memorizzare su una lista le etichette;
\item \textit{Map}: che contiene una funzione anch'essa denominata \textit{labels} ma che permette di estrarre tutti i valori di chiave da una lista associativa:
\end{itemize}
rappresentata nel seguente modo:
\begin{verbatim}
module Syntax : 
sig
   module Tree :
   sig
    type 'a tree = Empty | Node of 'a * 'a tree * 'a tree
    val labels : 'a tree -> 'a list
   end
end
module Map :
sig
 val labels : ('a * 'a) list -> 'a list
end
\end{verbatim}
Se non si fosse specificato in modo corretto il percorso del modulo al quale appartengono le due funzioni \textit{labels}, si sarebbe creata una ambiguit\`a nella definizione della tabella dei valori. Qualificando le funzioni, questi conflitti vengono risolti e si ottiene la tabella: 
\[
\begin{tabular}{|l|l|}
\hline
\textbf{Nome Funzione} & \textbf{Tipo} \\
\hline & \\							
\texttt{Syntax.Tree.labels} & \verb! 'a Syntax.Tree.tree! $\to$ \verb!'a list ! \\
 & \\
\texttt{Map.labels} 		& \verb! ('a * 'a) list! $\to$ \verb!'a list!\\
 & \\
 \hline
\end{tabular}
\]

Mentre per i tipi:

\[
\begin{tabular}{|l|l|}
\hline
\textbf{Nome Tipo} & \textbf{Definizione} \\
\hline & \\
\texttt{Syntax.Tree.tree}	& \verb! Syntax.Tree.Empty ! \\
							& \verb! | Syntax.Tree.Node of 'a !\\
							& \verb!     * 'a Syntax.Tree.tree!\\
							& \verb!     * 'a Syntax.Tree.tree!\\
 & \\ 
 \hline 
\end{tabular}
\]

Come verr\`a mostrato nella sezione~\ref{utilizzi.tool}, mediante il flag \textit{-debug} \`e possibile visualizzare il contenuto di queste due tabelle.

\section {Trasformazione dei tipi}
Fino a questo punto si \`e parlato di come il tool rappresenta le interfacce, si \`e descritto come la rappresentazione ad albero sintattico viene tradotta in forma tabellare ma non si \`e mostrata la grammatica dei tipi che viene utilizzata. Come descritto precedentemente, la grammatica di questi tipi ``utente'' rispecchia in modo preciso la struttura dei tipi utilizzati dal linguaggio $\OCaml$, questa \`e definita come segue:
\[
\begin{array}{ll}
\begin{array}[t]{rcl}
  \ctype & ::= & \tvar \\
    & | & \ctype \to \ctype \\
    & | & \ctype_1 \times \cdots \times \ctype_n \\
    & | & \sequence{\ctype} \tref \\
    \\
    \tref & ::= & \sequence{\tvar}B \\
  \end{array}
&
\begin{array}[t]{rcl}
    B & ::= & \tabstract \\
    & | & \ctype \\
    & | & \{ \field_1 : \ctype_1, \dots, \field_n : \ctype_n \} \\
    & | & [ \ctor_1 : \ctype_1; \dots; \ctor_n : \ctype_n ] \\
\end{array}
\end{array}
\]            

Un tipo $T$ pu\`o essere una variabile $\alpha$, un tipo freccia, una tupla o un riferimento $R$. In questo caso avremo una serie di variabili che precedono il corpo $B$ il quale potr\`a essere astratto, un alias $T$, un record oppure un tipo algebrico. 

In questa struttura i tipi algebrici e tipi record sono accessibili per mezzo di riferimenti (produzione $T ::= (T_1,...,T_n)R $). Per adattare questa grammatica al sistema di tipi mostrato nel capitolo~\ref{isomorfismi}, si \`e deciso di attuare una traduzione nella quale i tipi algebrici sono inseriti direttamente all'interno del tipo piuttosto che essere accessibili per mezzo di una produzione e i tipi record sono tradotti in tipi tupla.
La traduzione ha quindi come scopo la trasformazione del tipo utente, che rappresenta i tipi utilizzati dal linguaggio $\OCaml$, in tipi interni adatti al calcolo degli isomorfismi ed \`e effettuata come segue:
\[
\begin{array}{rcll}
  \trans{\tvar}{\env} & = & \tvar \\
  \trans{\ctype_1 \to \ctype_2}{\env} & = & \trans{\ctype_1}{\env} \to \trans{\ctype_2}{\env} \\
  \trans{\ctype_1 \times \cdots \times \ctype_n}{\env} & = & \trans{\ctype_1}{\env} \times \cdots \times \trans{\ctype_n}{\env} \\
  \trans{\sequence{\ctype}\tref}{\env} & = & \tvar \hfill (\sequence{\ctype}\tref, \tvar) \in \env \\

  \trans{\sequence{\ctype}\tref}{\env} & = & (\trans{\ctype_1}{\env}\cdots\trans{\ctype_n}{\env})\tref \ \hfill \text{($\tref = \sequence{\tvar}\tabstract$)} \\
  \trans{\sequence{\ctype}\tref}{\env} & = & \mu\tvar.\trans{B\subst{\ctype_1}{\tvar_1}\cdots\subst{\ctype_n}{\tvar_n}}\\&&{\env \cup \{ (\sequence{\ctype}\tref, \tvar) \}} \\
  & & \hfill \text{($\tref = \sequence{\tvar}B$, $\tvar$ fresh)} \\
  \trans{\{\field_1:\ctype_1, \dots, \field_n:\ctype_n\}}{\env} & = & \trans{\ctype_1}{\env} \times \cdots \times \trans{\ctype_n}{\env} \\
  \trans{[\ctor_1:\ctype_1; \dots; \ctor_n:\ctype_n]}{\env} & = & [\ctor_1:\trans{\ctype_1}{\env}; \dots; \ctor_n : \trans{\ctype_n}{\env}] \\
\end{array}
\]

Per descrivere come avviene questa traduzione si riprenda l'esempio dell'albero polimorfo descritto in precedenza:
\begin{ScriptMath}
type 'a tree = Empty | Node of 'a * 'a tree * 'a tree
\end{ScriptMath}
questo verrebbe rappresentato, attraverso la grammatica dei tipi utente, tramite:
\begin{ScriptMath}
type tree = ('a) [Empty: unit | Node: 'a * 'a tree * 'a tree]
\end{ScriptMath}
che come si pu\`o notare \`e costituito da un riferimento che possiede la struttura $\sequence{\tvar}B$. A questo livello i tipi $\tint$ e $\tunit$ sono considerati come astratti.
Si supponga inoltre che all'interno del codice compaia un 
\[
(\tint) \texttt{tree}
\]
La traduzione di questo tipo si basa sull'ambiente $\env$ detto di \textit{memoizzazione}, nel quale vengono memorizzati i tipi che sono gi\`a stati tradotti e quelli astratti, ovvero quelli predefiniti del linguaggio $\OCaml$.
L'idea \`e che partendo dall'ambiente che contiene solo i tipi predefiniti che si sono incontrati:
\[
\trans{(\tint) \texttt{tree}}_\env
\]
dove $\env$ \`e composto da:
\[
\begin{array}{r@{}rclr@{}}
	\env = \{&\tint &\mapsto& \texttt{abstract};&\\
	&\tunit &\mapsto & \texttt{abstract}&\}
\end{array}	
\]
ovvero dalla situazione in cui non si hanno informazioni riguardo traduzioni precedenti, per tradurre un riferimento sono possibili le situazioni:
\begin {itemize}
\item $(\sequence{\ctype}\tref, \tvar) \in \env$: la traduzione \`e gi\`a stata effettuata e quindi questa appartiene all'ambiente di memoizzazione.
\item $(\tref = \sequence{\tvar}\tabstract)$: si \`e in presenza di un tipo astratto.
\item $(\tref = \sequence{\tvar}B$, $\tvar\  \text{fresh})$: la traduzione di un tipo non astratto deve essere ancora effettuata.
\end {itemize}
nel caso specifico dell'esempio, l'ambiente di memoizzazione contiene esclusivamente le definizioni dei tipi astratti, quindi la prima regola non pu\`o essere utilizzata, non essendo un tipo astratto \`e necessario utilizzare la terza regola la quale generer\`a un tipo della forma:
\[
\mu\beta. \trans{ [\texttt{Empty} : \tunit; \texttt{Node} : (\tint \times ((\tint) \texttt {tree} \times (\tint) \texttt{tree}))]}_\env
\]
dove \`e stata sostituita la variabile $\alpha$ con il tipo $\tint$ all'interno del corpo $B$ del tipo. L'ambiente di memoizzazione, dopo questa sostituzione, viene esteso con la regola ${\{(\tint) \texttt{tree} \mapsto \beta \}}$ ottenendo quindi:
\[
\begin{array}{r@{}rclr@{}}
	\env = \{&\tint &\mapsto& \texttt{abstract};&\\
	&\tunit &\mapsto & \texttt{abstract};&\\
	&(\tint) \texttt{tree} &\mapsto& \beta &\}
\end{array}	
\]
che servir\`a a ricordarsi nelle traduzioni successive che il tipo $(\tint) \texttt{tree}$ dovr\`a essere tradotto con $\beta$. Se non fosse stato utilizzato questo ambiente ogni volta incontrato un tipo $(\tint) \texttt{tree}$ sarebbe stato necessario effettuare nuovamente questa espansione cadendo, nel caso di tipi ricorsivi, in un loop infinito.

Il passo successivo \`e quello di entrare all'interno del tipo algebrico (si vedano le parentesi $\trans{\ }$) dove, applicando la regola che riguarda i tipi algebrici $[\ctor_1:\trans{\ctype_1}{\env}; \dots; \ctor_n : \trans{\ctype_n}{\env}]$ \`e necessario tradurre i tipi dei due costruttori, ovvero:
\[
\mu\beta. [\texttt{Empty}:\trans{\tunit}; \texttt{Node}:\trans{(\tint \times ((\tint) \texttt {tree} \times (\tint) \texttt{tree}))}]
\]
La traduzione del tipo del primo costruttore $\trans{\tunit}$, che abbiamo detto essere considerato come astratto, per la seconda regola di traduzione dei riferimenti diverr\`a semplicemente $\tunit$. Per quanto riguarda il tipo del secondo costruttore $\trans{(\tint \times ((\tint) \texttt {tree} \times (\tint) \texttt{tree}))}$, avendo a disposizione all'interno dell'ambiente di memoizzazione l'informazione che il tipo $(\tint) \texttt{tree}$ deve essere tradotto con $\beta$, per la regola di gestione delle tuple e per la prima regola di traduzione dei riferimenti questo verr\`a trasformato in $(\tint \times (\beta \times \beta))$, ottenendo cos\`i come risultato il tipo:
\[
\mu\beta. [\texttt{Empty}:\tunit; \texttt{Node}:(\tint \times (\beta \times \beta))]
\] 
equivalente a quello esposto nel capitolo~\ref{isomorfismi} a meno del nome della variabile di ricorsione.

La traduzione dei tipi avviene quindi nel seguente modo:
\begin {itemize}
\item le variabili di tipo vengono semplicemente riscritte nel tipo interno;
\item in un tipo freccia vengono tradotti gli operandi;
\item un tipo tupla viene costruito traducendo gli elementi che lo compongono;
\item un riferimento la cui traduzione compare all'interno dell'ambiente di memoizzazione viene tradotto mediante il valore memorizzato;
\item un riferimento ad un tipo astratto viene tradotto trasformando gli elementi dei tipi $T_1, \dots, T_n$ che lo compongono;
\item un riferimento non astratto la cui traduzione non \`e presente nell'ambiente di memoizzazione viene tradotto con il corpo del riferimento al quale viene sostituita ogni occorrenza di $T_1, \dots, T_n$ con $\alpha_1, \dots, \alpha_n$;
\item i record vengono tradotti in tuple;
\item in un tipo algebrico vengono tradotti i tipi dei costruttori.
\end {itemize}
Alla fine di questa fase di traduzione si otterranno dei tipi nella forma descritta nella teoria degli isomorfismi mostrata nel capitolo~\ref{isomorfismi}.

\section {Calcolo delle distanze}
\label{sez:calcolo.equivalenze}
Tramite le fasi precedenti si \`e riusciti ad ottenere una tabella che contiene i tipi interni di tutte le funzioni qualificate che sono presenti all'interno di un progetto. A questo punto \`e possibile procedere con la fase di calcolo della distanza.

L'obiettivo che si vuole raggiungere \`e quello di ottenere, a partire dalle tabelle che contengono le funzioni dei due progetti, un valore che indichi il grado di similitudine tra queste, in base alla definizione di isomorfismo descritta precedentemente.
Per fare questo \`e stato necessario individuare il numero di funzioni, all'interno di un progetto, che condividono lo stesso tipo, ovvero si \`e definita una sorta di ``inverted map'' nel quale la chiave di ricerca non \`e pi\`u la funzione bens\`i il tipo.

La tabella ottenuta nelle fasi precedenti:
\[
\begin{array}{|ll|}
\hline
\textbf{Funzione} & \textbf{Tipo} \\
v_1		& t_1 		\\
v_2		& t_2		\\
v_3		& t_1		\\
v_4		& t_4	 	\\
\hline
\end{array}
\]
\`e stata pertanto trasformata nel seguente modo:
\[
\begin{array}{|ll|}
\hline
\textbf{Tipo} & \textbf{Funzione} \\
t_1		& v_1, v_3 	\\
t_2		& v_2		\\
t_4		& v_4		\\
\hline
\end{array}
\]
ottenuta questa rappresentazione per entrambi i file da confrontare, l'idea \`e 
quella di partizionare le tabelle delle funzioni in base alla relazione di equivalenza che si desidera utilizzare\footnote{Nel caso del progetto verr\`a utilizzata la relazione esposta nell'ambito degli isomorfismi di tipo descritti nel capitolo precedente}, facendo in modo che due valori appartengano ad una partizione se i rispettivi tipi sono equivalenti.
Verr\`a quindi creata un'unica tabella contenente, come chiave, i tipi dei due file raggruppati in base alla relazione di isomorfismo e, come valore, il numero di funzioni per ciascun progetto che possiedono un determinato tipo.

In questo modo risulta essere estremamente semplice confrontare i programmi tenendo conto o ignorando il numero di valori con un certo tipo, cosa che non \`e evidente se si utilizza la rappresentazione originaria.
Come vedremo nella sezione~\ref{utilizzi.tool} mediante il flag \textit{show} \`e possibile mostrare a video tutti i tipi presenti nei due progetti e, per ciascuno di essi, le funzioni che li utilizzano.
Ad esempio supponendo di avere due progetti composti come segue:
\[
\begin{array}{|rl||rl|}
\hline
\textbf{Tipo} & \textbf{Progetto 1} & \textbf{Tipo} & \textbf{Progetto 2} \\
t_1: & f_1, f_3		& u_1: & g_1, g_2 		\\
t_2: & f_2			& u_2: & g_6  			\\
t_3: & f_4, f_5		& u_3: & g_3			\\
\hline
\end{array}
\]
e supponendo che in base alla relazione di equivalenza/isomorfismo i tipi $t_1$,$u_1$ e $t_2$,$u_2$ siano equivalenti/isomorfi, si ottiene la tabella:
\[
\begin{array}{|rll|}
\hline
\textbf{Tipo} & \textbf{Progetto 1} & \textbf{Progetto 2} \\
t_1: & f_1, f_3 	& g_1, g_2 		  	\\
t_2: & f_2			& g_6 				\\
t_3: & f_4, f_5		& -					\\	
u_3: & - 			& g_3				\\
\hline
\end{array}
\]
dove sono mostrate le partizioni composte da tipi isomorfi e dove sono indicate, per ciascun progetto, le funzioni che appartengono a quella determinata partizione.
A questo livello, non \`e pi\`u importante il nome della funzione, il nostro scopo \`e unicamente quello di individuare un valore che possa rappresentare il grado di similitudine tra due progetti, pertanto le classi dei tipi verranno caratterizzate dal numero di funzioni che vi appartengono. Ogni progetto verr\`a cio\`e caratterizzato da una lista di numeri interi:
\[
\begin{array}{|rll|}
\hline
\textbf{Tipo} & \textbf{Progetto 1} & \textbf{Progetto 2} \\
t_1: & 2 		& 2 		  		\\
t_2: & 1		& 1 				\\
t_3: & 2		& 0					\\	
u_3: & 0 		& 1					\\
\hline	
\end{array}
\]
che rappresenta il numero di funzioni per ciascun tipo.

A questo punto il problema si \`e tradotto nell'individuazione di una tecnica che permettesse di calcolare il grado di similarit\`a tra due popolazioni di campioni definite in questo modo.
La teoria della \textit{histogram distance}~\cite{hist_distance} ha permesso di risolvere agevolmente questo problema individuando una serie di distanze che consentono di calcolare in modi diversi questo valore, le metriche utilizzate nel progetto sono esposte in tabella~\ref{tab:dist}.
\begin{table}
\[
\begin{array}{|l|l|}
\hline
\textbf{Distanza} & \textbf{Valore} \\
\hline
\textit{Soergel} 	& d_{sg} = {{\displaystyle\sum_{i=1}^d |P_i - Q_i|}\over{\displaystyle\sum_{i=1}^d \max(P_i, Q_i)}}\\
& \\
\textit{Canberra}	& d_{Can} = \displaystyle\sum_{i=1}^d { {|P_i - Q_i|}\over{P_i + Q_i}}\\
& \\
\textit{Sharing} 	& d_{sha} = \min \left({{\displaystyle\sum_{i=1}^d {\max(0, (P_i - Q_i))}} \over {\displaystyle\sum_{i=1}^d P_i}}, {{\displaystyle\sum_{i=1}^d {\max(0, (Q_i - P_i))}} \over {\displaystyle\sum_{i=1}^d Q_i}}\right)\\
& \\
\hline
\end {array}
\]
\caption{Tabella delle distanze}
\label{tab:dist}
\end{table}

Si pu\`o chiaramente notare come tutte le distanze calcolino un vettore che rappresenta il grado di originalit\`a di ciascun tipo:
\[
\begin{array}{lr}
V_{\textit{diff}} = [|P_0 - Q_0|, |P_1 - Q_1|, \dots, |P_n - Q_n|]
\end{array}
\] 
ovvero effettuano la differenza in modulo, per ogni tipo $i$, del numero di funzioni tra i due progetti, ottenendo in questo modo un vettore delle differenze il quale rappresenta la distanza, di ogni tipo del progetto $P$, dal corrispondente tipo del progetto $Q$. 

Supponendo, ad esempio, di avere a disposizione una mappa dei tipi definita in questo modo:
\[
\begin{array}{|rll|}
\hline
\textbf{Tipo} & \textbf{Progetto 1(P)} & \textbf{Progetto 2(Q)} \\
t_1: & 2 		& 2 		  		\\ 
t_2: & 1		& 1 				\\ 
t_3: & 5		& 0					\\ 	
u_3: & 0 		& 5					\\
\hline
\end{array}
\]
si otterrebbe il seguente vettore delle differenze:
\[
V_{\textit{diff}} = [0; 0; 5; 5].
\]
Nel caso del tipo $t_1$, ad esempio, il valore $0$ indicher\`a intuitivamente che tra i due progetti vi \`e una totale condivisione delle funzioni. 
Pi\`u sar\`a alto il valore pi\`u questo rappresenter\`a una caratteristica di originalit\`a, ad esempio per $t_3$ e $u_3$ il valore $5$, descrive il fatto che sono presenti cinque funzioni in pi\`u nell'uno o nell'altro progetto.

Nei prossimi paragrafi si descriver\`a il metodo utilizzato per calcolare le tre distanze e verr\`a descritta l'intuizione che vi \`e alla base.

\paragraph{Distanza Soergel} questa distanza inizialmente calcola il grado totale di originalit\`a tra i due progetti
\[
G_{orig} = \displaystyle\sum_{i=1}^d {|P_i - Q_i|}
\] 
sommando ciascun componente del vettore delle differenze in modo da ottenere un numero che rappresenta la quantit\`a di funzioni che sono ritenute come ``originali'' ovvero il numero di valori che non sono condivisi. 
Successivamente normalizzer\`a questo indice sulla somma degli elementi di un vettore ottenuto considerando, per ogni tipo, il valore massimo tra i due progetti.
Ad esempio supponendo di avere:
\[
\begin{array}{|rll|}
\hline 
\textbf{Tipo} & \textbf{Progetto 1(P)} & \textbf{Progetto 2(Q)}  \\
t_1: & 2 		& 0 	\\ 
t_2: & 0		& 2 	\\ 
\hline 
\end{array}
\]
i due vettori risultanti sarebbero:
\[
\begin{array}{l}
V_{\textit{diff}} = [2;2] \\
V_{\max} = [2;2]	\\
\end{array}
\]
sommando gli elementi di questi vettori ed effettuandone la differenza si ottiene il valore $1$ che descrive la situazione in cui i due progetti sono considerati a distanza massima.
Un altro esempio \`e:
\[
\begin{array}{|rll|}
\hline 
\textbf{Tipo} & \textbf{Progetto 1(P)} & \textbf{Progetto 2(Q)}  \\
t_1: & 2 		& 2 	\\ 
t_2: & 1		& 2 	\\
\hline  
\end{array}
\]
i cui vettori risultanti sono:
\[
\begin{array}{l}
V_{\textit{diff}} = [0;1] \\
V_{\max} = [2;2]	\\
\end{array}
\]
in questo caso la somma degli elementi del vettore delle differenze, che rappresenta il grado di originalit\`a tra i due progetti, risulta essere $1$ ovvero \`e presente una sola funzione ritenuta come originale. 
Effettuando la differenza di questo valore con la somma degli elementi del vettore $V_{\max}$ si ottiene il valore $0,25$ che indica che su un totale di quattro funzioni solo una non \`e condivisa da entrambi progetti. 

A questo punto \`e possibile chiarire il fatto per cui viene preso il valore massimo tra i due tipi. Si consideri infatti il tipo $t_2$; dal vettore delle differenze \`e possibile dedurre che una sola funzione sia ritenuta genuina. 
Per riuscire a normalizzare questo valore \`e necessario domandarsi quante sono in totale le funzioni che vengono prese in considerazione. Non \`e sbagliato pensare che questo numero sia pari a tre, ovvero alla somma $P_i + Q_i$, tuttavia all'interno di queste tre funzioni ve ne sono due che sono considerate equivalenti, il massimo tra $P_i$ e $Q_i$ permette quindi di identificare il numero totale dei valori distinti. 

La distanza Soergel, quindi, permette di ottenere un valore di distanza compreso tra $0$ (nel caso in cui entrambi progetti abbiano lo stesso numero di funzioni per ciascun tipo) e $1$ (nel momento in cui non ci sia nessuna condivisione di valori) calcolato normalizzando il numero di funzioni considerate originali sul numero totale di quelle non ripetute.

\paragraph{Distanza Canberra:} questa distanza a differenza della Soergel normalizza ciascun valore $i$ del vettore delle differenze, sul numero totale di funzioni presenti nei due progetti per quel determinato tipo $i$. 
Questo permette di ottenere un valore che rappresenta il numero di funzioni inserite in pi\`u rispetto al numero totale delle funzioni dei due progetti.  Riprendendo gli esempi precedenti avremo:
\[	
\begin{array}{|rlll|}    
\hline
\textbf{Tipo} & \textbf{Progetto 1(P)} & \textbf{Progetto 2(Q)} & \textbf{Valore normalizzato per $i$} \\
t_1: & 2 		& 0 	& 1	  		\\ 
t_2: & 0		& 2 	& 1 		\\ 
\hline
\end{array}
\]
ovvero per ciascun tipo si otterr\`a un valore compreso tra $0$ e $1$ dove il valore $0$ rappresenta la situazione in cui le funzioni di quel tipo sono state presumibilmente plagiate, mentre il valore $1$ rappresenta la situazione in cui non vi \`e alcuna condivisione di funzioni per un determinato tipo. Il risultato finale sar\`a ottenuto come la somma degli elementi del vettore delle differenze normalizzate ($d_{P,Q} = 1 + 1 = 2$). 

La metrica Canberra restituir\`a pertanto un valore che \`e dipendente dal numero di tipi presenti nei due progetti. 
Il secondo esempio \`e descritto dalla tabella:
\[
\begin{array}{|rlll|}                
\hline
\textbf{Tipo} & \textbf{Progetto 1(P)} & \textbf{Progetto 2(Q)} & \textbf{Valore normalizzato per $i$} \\
t_1: & 2 		& 2 	& 0	  		\\ 
t_2: & 1		& 2 	& 1/3 		\\   
\hline
\end{array}
\]
in questo caso il valore $0$ per il tipo $t_1$ \`e un chiaro sintomo di una possibile copiatura, mentre il valore $1/3$ per $t_2$ indica che su un totale di $3$ funzioni una sola risulta essere originale, ovvero non \`e presente in uno dei due programmi. 
A differenza della Soergel, la normalizzazione avviene sul totale delle funzioni, verranno cio\`e considerati anche i valori che sono ritenute equivalenti. 

In conclusione la metrica Canberra permetter\`a di ottenere un risultato compreso tra $0$ (nessuna differenza) e $n$ (massima differenza) dove $n$ rappresenta il numero di tipi presenti nei due progetti. 

\paragraph{Distanza sharing:} questa distanza indica il grado di condivisione di due progetti ed \`e ottenuta prendendo il valore minimo tra la somma dei valori positivi del vettore delle differenze normalizzato sul numero di valori di $P$ e la somma dei valori positivi del vettore delle differenze $Q_i - P_i$ normalizzato sul numero di valori di $Q$.
Per descrivere l'intuizione che sta alla base di questa metrica si consideri il seguente esempio:
\[
\begin{array}{|rll|}
\hline
\textbf{Tipo} & \textbf{Progetto 1(P)} & \textbf{Progetto 2(Q)}  \\
t_1: & 0 		& 2 \\ 
t_2: & 2		& 1 \\ 
t_3: & 2		& 2 \\
\hline 
\end{array}
\]
dove i valori di condivisione dei due progetti sono:
\[
\begin{array}{|rll|}
\hline
\textbf{Tipo} & \textbf{Condivisione P con Q} & \textbf{Condivisione Q con P} \\
t_1: 		  & 0	& 2	\\ 
t_2: 		  & 1 	& 0	\\ 
t_3: 		  & 0 	& 0	\\
\hline 
\end{array}
\]
come si pu\`o notare i valori di condivisione, che sono ottenuti considerando il valore massimo tra $0$ e la differenza $P_i - Q_i$ per il progetto $P$ o $Q_i - P_i$ per $Q$, rappresentano il numero di funzioni che vengono condivise nel progetto $P$ o nel progetto $Q$, ovvero indicano che, nel caso del tipo $t_2$, il progetto $P$ condivide con $Q$ un solo valore. 

Per ottenere la distanza questi verranno sommati e normalizzati sul numero totale di funzioni di ciascun progetto preso come riferimento, il risultato sar\`a il valore minimo tra queste due somme. 

Verr\`a considerato il valore minimo per tentare di individuare la situazione in cui un progetto viene incluso all'interno di un altro. Questo nella pratica pu\`o succedere nel momento in cui uno studente plagia un programma e ne aggiunge delle funzionalit\`a non specificatamente richieste.

Ad esempio nella tabella:
\[
\begin{array}{|rll|}
\hline
\textbf{Tipo} & \textbf{Progetto 1(P)} & \textbf{Progetto 2(Q)}  \\
t_1: & 0 		& 2 	\\ 
t_2: & 2		& 2 	\\ 
t_3: & 2		& 2 	\\
\hline 
\end{array}
\]
\`e mostrata chiaramente la situzione in cui il progetto $P$ \`e un sottoinsieme di $Q$ $(P \subset Q)$, i valori di condivisione saranno:
\[
\begin{array}{|rll|}
\hline
\textbf{Tipo} & \textbf{Condivisione P con Q} & \textbf{Condivisione Q con P} \\
t_1: & 0  	& 2	\\ 
t_2: & 0 	& 0	\\ 
t_3: & 0 	& 0	\\ 
\hline
\end{array}
\]
Il progetto $Q$ condivide quindi tutte le funzionalit\`a di $P$ ma vi aggiunge due funzioni di tipo $t_1$.
Sotto queste condizioni	il grado di distanza tra i progetti $P$ e $Q$ \`e pari a $0$, ovvero i progetti vengono considerati plagiati. 

La distanza sharing permette quindi di ottenere un valore compreso tra $0$, nel momento in cui un progetto \`e completamente incluso all'interno di un altro, e $1$, valore che si ottiene se i due progetti non condividono alcuna funzione.

\section {Esempi di utilizzo del tool}
\label {utilizzi.tool}
Il tool \textit{isotype} realizzato\footnote{Il tool \`e disponibile liberamente (licenza GNU GPL) on-line all'indirizzo:
\texttt{http://code.google.com/p/applied-cs-graduation-projects/source\-/browse/\#svn/} all'interno del trunk \texttt{Isomorfismi}} per la misura del livello di similarit\`a di programmi funzionali mediante isomorfismi di tipo opera a linea di comando nel seguente modo:
\begin{center}
\verb!./isotype --<flags> <interfacce>!
\end{center}
presa cio\`e in ingresso una lista di interfacce, calcoler\`a le distanze di ciascun progetto con tutti gli altri, creando una matrice triangolare di similarit\`a della forma:
\[
\begin{array}{|c|c|c|c|c|}
\hline
\hspace{7mm}& X_{1,2} & X_{1,3} & X_{1,4} & X_{1,5} \\
\hline
 &  & X_{2,3} & X_{2,4} & X_{2,5}\\
\hline
 &  &  & X_{3,4} & X_{3,5} \\
\hline
 & & & & X_{4,5}\\
\hline
 & & & & \\ 
\hline
\end {array}
\]
dove la cella $X_{i, j}$ rappresenta la distanza del progetto $i$ da $j$.\footnote{Naturalmente, essendo il concetto di isomorfismo simmetrico non \`e necessario calcolare la distanza del progetto $j$ da quello $i$ in quanto questo valore sar\`a uguale a $X_{i,j}$. Sono stati inoltre trascurati i valori $X_{i,j}$ dove $i=j$}
Il numero totale di confronti da effettuare per popolare la matrice di similarit\`a su un insieme di $n$ interfacce risulta essere quindi pari a 
\[
n_{test} = {{n \times (n-1)}\over{2}}
\]
ovvero, se si suppone di dover confrontare 10 progetti verranno restituiti $45$ valori.

\subsection{Flags per il controllo del funzionamento del tool}
\`E possibile agire sul funzionamento dell'applicazione mediante i seguenti flags:
\[
\begin{tabular}{|l|l|}
\hline
\texttt{debug} 	& Stampa a video informazioni di debug \\ 
\texttt{show}		& Mostra le differenze tra le interfacce \\
\texttt{focus} 	& Calcola equivalenza su una interfaccia \\
\texttt{distance}	& Setta la metrica di distanza utilizzata \\
\hline
\end{tabular}
\]
 
Il flag \texttt{distance} \`e il pi\`u significativo in quanto permette di impostare la metrica di distanza che si desidera utilizzare scegliendo tra le tre descritte nella sezione precedente, se non viene specificata nessuna distanza verr\`a utilizzata la metrica Soergel che, come vedremo nei test effettuati, \`e risultata essere quella che permette di ottenere valori di distanza realistici e normalizzati tra $0$ e $1$.

Mediante l'opzione \texttt{debug} \`e possibile fare in modo che venga mostrato il contenuto delle tabelle che contengono tutte le funzioni e le definizioni dei tipi presenti in ciascun progetto. Verr\`a mostrato lo stato di questi valori sia in ingresso che in uscita al modulo resolver, ovvero verr\`a mostrata la struttura dell'AST e il contenuto della tabella dove sono state effettuate le operazioni di qualificazione descritte in questo capitolo.

Mediante l'opzione \texttt{show} \`e possibile mostrare le differenze tra le interfacce, verranno cio\`e mostrati i tipi individuati all'interno dei due progetti e verranno elencate le funzioni, per ciascun progetto, che utilizzano quel tipo.
Ad esempio le interfacce:
\[
\begin{array}{ll}
\textbf{Progetto 1} & \textbf{Progetto 2}   \\
\verb! module A :			!&\verb!  module B :		!  	\\				
\verb! sig					!&\verb!  sig				!  	\\
\verb!   val a_g : int		!&\verb!    val b_g : int	!  	\\
\verb!   val a_h : bool		!&\verb!    val b_h : bool	!  	\\
\verb!   val a_i : string	!&\verb!    val b_i : char	!  	\\
\verb! end  				!&\verb!  end  				!  \\
\end{array}
\]
Mostreranno a video:
\begin{verbatim}
TYPE char
 0> 
 1> B.b_i
TYPE bool
 1> A.a_h
 1> B.b_h
TYPE int
 1> A.a_g
 1> B.b_g
TYPE string
 1> A.a_i
 0> 
(1,2) 0.500000
\end{verbatim}
Questa funzionalit\`a risulta essere estremamente importante dal momento in cui il valore numerico restituito dal tool rappresenta esclusivamente un indice di distanza che deve portare l'utilizzatore ad individuare i casi in cui \`e necessario effettuare una analisi dettagliata del codice sorgente. Questo flag permette di mostrare tutti tipi presenti nei due progetti e, per ciascuno di essi, il numero ed il nome delle funzioni che li utilizzano. Nel momento in cui si desidera verificare la presenza effettiva di una situazione di plagio questa rappresentazione permette di individuare con facilit\`a le funzioni sospette.

Tramite il flag \texttt{focus} \`e possibile specificare all'applicazione che si desidera effettuare il confronto di un solo progetto, piuttosto che calcolare la distanza tra tutte le interfacce, mediante questa opzione \`e possibile fare in modo che il primo progetto della lista venga confrontato con gli altri.
Ad esempio, supponendo di voler confrontare l'interfaccia 0 con la 1, 2, 3, 4, 5 il comando sarebbe:
\begin{center}
\verb! ./isotype --focus 0 1 2 3 4 5!
\end{center}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "tesi"
%%% End: 
